# 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
# 除k取余法

# 执行用时：
# 228 ms
# , 在所有 Python3 提交中击败了
# 5.23%
# 的用户
# 内存消耗：
# 15.7 MB
# , 在所有 Python3 提交中击败了
# 43.00%
# 的用户
from typing import List


class Solution:
    def countBits(self, n: int) -> List[int]:
        def DtoB(num):
            if num == 0:
                return 0
            count = 0
            temp1 = num%2
            temp2 = num//2
            if temp1 == 1:
                count += 1
            return DtoB(temp2) + count
        res = []
        for  i in range(n+1):
            count = DtoB(i)
            res.append(count)
        return res

